#include<iostream>
#include<cstring>
#include<queue>
#include<pthread.h>
#include<semaphore.h>
#include<queue>
#include<sys/time.h>
using namespace std;
const int N = 10000, M = N*N;
int h[N], e[M], ne[M], w[M], idx;
queue<int>q;

void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
typedef pair<int, int> PII;
int st[N], dist[N];

int NUM_THREADS = 7;
int m_dist[N][8];
bool book[N];
pthread_mutex_t mutex;
sem_t sem_available;
int num_used;
typedef struct {
	int t_id;
	int cur_vertex;
}threadParam;

void* threadFunc(void* param) {
	threadParam* p = (threadParam*)param;
	int cur_index = p->cur_vertex;
	int t_id = p->t_id;
	for (int i = h[cur_index]; ~i; i = ne[i]) {
		int j = e[i];
		if (dist[j] > dist[cur_index] + w[i]) {
			m_dist[j][t_id] = min(m_dist[j][t_id],dist[cur_index] + w[i]);
			book[j] = 1;
			if (!st[j]) {
				pthread_mutex_lock(&mutex);
				q.push(j);
				st[j] = 1;
				pthread_mutex_unlock(&mutex);
			}
		}
	}
	sem_post(&sem_available);
	pthread_exit(NULL);
	return 0;
}
void SPFA(int n) {
	q.push(1);
	dist[1] = 0;
	st[1] = 1;
	while (!q.empty()) {
		int cur_size = q.size();
		while (cur_size--) {
			threadParam* param = new threadParam;
			int v = q.front();
			q.pop();
			st[v] = 0;
			param->cur_vertex = v;
			param->t_id = num_used++;
			sem_wait(&sem_available);
			pthread_t* handle = new pthread_t;
			pthread_create(handle, NULL, threadFunc, param);
		}
		for (int i = 0; i < NUM_THREADS; ++i)
			sem_wait(&sem_available);
		for (int i = 0; i < NUM_THREADS; ++i)
			sem_post(&sem_available);
		num_used = 0;

		for (int i = 1; i <= n; ++i) {
			if (!book[i])continue;
			book[i] = 0;
			for (int j = 0; j < NUM_THREADS; ++j)
				dist[i] = min(dist[i], m_dist[i][j]);
		}
	}
	for (int i = 1; i <= n; ++i)
		if (dist[i] >= 0x3f3f3f3f / 2)
			dist[i] = -1;
}
int main(int argc,char** args) {
	memset(dist, 0x3f, sizeof dist);
	memset(m_dist, 0x3f, sizeof m_dist);
	memset(h, -1, sizeof h);
	int n, m;
	cin >> n >> m;
	NUM_THREADS=args[1][0]-'0';
	for (int i = 0; i < m; ++i) {
		int a, b, c;
		scanf("%d%d%d",&a,&b,&c);
		add(a, b, c);
	}
	pthread_mutex_init(&mutex,NULL);
	sem_init(&sem_available, 0, NUM_THREADS);
	


    struct timeval t1,t2;
    double time=0.0;
	gettimeofday(&t1,NULL);
	////
	SPFA(n);
	////
	gettimeofday(&t2,NULL);
	time=(double)(t2.tv_sec-t1.tv_sec)*1000.0 + (double)(t2.tv_usec-t1.tv_usec)/1000.0;
	cout<< time;
}